package leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class code230 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }

        TreeNode() {
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
//        int n = scanner.nextInt();
        Integer[] arrayA = {4,2,5,null,3};
//        for (int i = 0; i < n; i++) {
//            arrayA[i] = scanner.next();
//        }
        TreeNode root = buildTree(arrayA);
        int k = scanner.nextInt();
        System.out.println(kthSmallest(root, k));
    }

    static ArrayList<Integer> list = new ArrayList<>();
    public static int kthSmallest(TreeNode root, int k) {
        midSelect(root);
        return list.get(k-1);
    }

    public static void midSelect(TreeNode treeNode){
        if (treeNode.left != null)
            midSelect(treeNode.left);
        list.add(treeNode.val);
        if (treeNode.right != null)
            midSelect(treeNode.right);
    }

    public static TreeNode buildTree(Integer[] arry){
        if(arry==null||arry.length==0){
            return null;
        }
       TreeNode root = new TreeNode(arry[0]);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int i = 1;
        while(!queue.isEmpty()){
            TreeNode currentNode = queue.poll();
            if(i<arry.length && arry[i]!=null){
                currentNode.left = new TreeNode(arry[i]);
                queue.offer(currentNode.left);

            }
            i++;
            if (i < arry.length && arry[i] != null){
                currentNode.right = new TreeNode(arry[i]);
                queue.offer(currentNode.right);

            }
            i++;

        }
        return root;
    }
}
